package 算法提高;/**
 * @author： li
 * @date： 2022-01-21 11:28
 * @version 1.0
 */

/*问题描述
　　小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，
   同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。
   已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。
输入格式
　　第一行包含一个整数n，代表楼的高度。

　　接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。
输出格式
　　输出1行，包含一个整数，表示所需的最短时间。
样例输入
5
3
5
1
8
4
样例输出
1
数据规模和约定
　　对20%的数据,n<=10
　　对40%的数据,n<=100
　　对60%的数据,n<=5000
　　对100%的数据,n<=10000
 */
import java.util.Scanner;
public class 秘密行动_DP {
    public static void main(String[] args) {
    Scanner sc =new Scanner(System.in);
    int n = sc.nextInt();
    int[] height =new int[n+1];
    int[][] dp =new int[n+1][3];
    for(int i=1;i<=n;i++)
        height[i]=sc.nextInt();
        dp[1][0]=height[1];//爬到第一层
        dp[1][1]=0;//跳到第一层
    for(int i=2;i<=n;i++){
        dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1])+height[i];//爬到第i层
        dp[i][1]=Math.min(dp[i-1][0],dp[i-2][0]);//跳到第i层
    }
    for(int i=0;i<=n;i++){
        System.out.println("第"+i+"层："+dp[i][0]+" "+dp[i][1]);
        System.out.println(" ");
    }
    int minTime = Math.min(dp[n][0],dp[n][1]);
        System.out.println(minTime);
    }
}
/*
* 解题思路：
到达第i层有两种方式：
dp[i][0]=h[i];//爬到第i层
dp[i][1]=0;//跳跃到第i层

所以，到达第i层的时间计算有两个状态转移方程：
1.爬到第i层时，达到第i-1层有两种方式，即：爬到第i-1层，跳跃到第i-1层；
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+h[i];

2.跳跃到第i层时，有两种方式跳跃到第i层，从第i-1层跳跃或者从第i-2层跳跃，那么，达到第i-1层或第i-2层只能是爬上去的；
dp[i][1]=min(dp[i-1][0],dp[i-2][0]);

最后，计算两种状态哪个所需时间最少。
min(dp[n][0],dp[n][1])
*/